package 牛客.字符串;

/*
    对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
    给定字符串A以及它的长度n，请返回最长回文子串的长度。
    示例1   输入"abc1234321ab",12     返回值7
 */
public class 最长回文子串 {
    public int getLongestPalindrome(String A, int n) {
        if(n <= 1)
            return n;
//暴力法：
//        for (int i = n; i > 0; i--) {
//            for (int j = 0; j <= n - i; j++) {
//                String sub = A.substring(j, i + j);//子串
//                System.out.println(sub);
//                int count = 0;
//                for (int k = 0; k < sub.length() /  2; k++) {
//                    if(sub.charAt(k) == sub.charAt(sub.length() - k -1))
//                        count++;
//                }
//                if(count == sub.length() / 2)
//                    return sub.length();
//            }
//        }
        //动态规划：
        /*
         * 用一个二维boolean矩阵T[i][j]来记录从位置i到j是否为回文子串，
         * 因为是从i到j，所以实际上只需要对下三角矩阵进行判断
         * T[i][j]是子串成立的条件：T[i+1][j-1]==true 或 j - i < 2
         * 每次比较完则判断更新一次长度
         */
        char[] chars = A.toCharArray();
        boolean[][] T = new boolean[n][n];  //默认值为false
        int len = 0;
        for (int i = 0; i < n; i++) {   //单个字符也是回文串
            T[i][i] = true;
        }
        for(int i = n - 2; i >= 0; i--){  // 因为是从i到j，所以实际上只需要对下三角矩阵进行判断
            for (int j = i + 1; j < n; j++) {
                if(chars[i] == chars[j] && (T[i+1][j-1] || j-i < 2))
                    T[i][j] = true;  //  T[i][j]是子串成立的条件：T[i+1][j-1]==true 或 j - i < 2
                else
                    T[i][j] = false;
                if(T[i][j] && j - i + 1 > len)  //每次比较完则判断更新一次长度
                    len = j - i + 1;
            }
        }
        return len;
    }

    public static void main(String[] args) {
        String A = "abc1234321ab";
        int n = 12;
        最长回文子串 obj = new 最长回文子串();
        System.out.println(obj.getLongestPalindrome(A, n));
    }
}
